package com.yun.algorithmproblem.leetcodenotcomplete;

import java.util.Scanner;

public class PollardRho {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入一个正整数: ");
        long number = scanner.nextLong();
        scanner.close();

        System.out.print("质因子为：");
        if (number <= 1) {
            System.out.println("请输入一个大于1的正整数。");
        } else if (number <= 1e8) {
            trialDivision(number);
        } else {
            pollardRho(number);
        }
    }

    // 试除法
    public static void trialDivision(long n) {
        for (long divisor = 2; divisor * divisor <= n; divisor++) {
            while (n % divisor == 0) {
                System.out.print(divisor + " ");
                n /= divisor;
            }
        }
        if (n > 1) {
            System.out.print(n + " ");
        }
    }

    // Pollard Rho算法
    public static void pollardRho(long n) {
        if (n <= 1) {
            return;
        }

        if (n % 2 == 0) {
            System.out.print("2 ");
            pollardRho(n / 2);
            return;
        }

        long x = 2, y = 2, d = 1;
        while (d == 1) {
            x = g(x, n);
            y = g(g(y, n), n);
            d = gcd(Math.abs(x - y), n);
        }

        if (d == n) {
            System.out.print(n + " ");
        } else {
            pollardRho(d);
            pollardRho(n / d);
        }
    }

    // 辗转相除法计算最大公约数
    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    // Pollard Rho算法的g函数
    public static long g(long x, long n) {
        return (x * x + 1) % n;
    }

}
